package Graph.Medium;

public class LC0547 {
    /**
     * 无向无权图
     * 利用深度优先遍历遍历顶点；使用一个for循环检查是否有未遍历的顶点，如有，从此顶点开始深度优先遍历；
     * 深度优先遍历的次数就是连通分量的个数，也是“省份”的数量
     */
    public int findCircleNum(int[][] isConnected) {
        int nComponents = 0;
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                nComponents++;
                dfs(isConnected, i, visited);
            }
        }

        return nComponents;
    }

    private void dfs(int[][] matrix, int startVex, boolean[] visited) {
        visited[startVex] = true;
        int n = matrix.length;
        for (int j = 0; j < n; j++) {
            if (matrix[startVex][j] > 0 && !visited[j]) dfs(matrix, j, visited);
        }
    }
}
